﻿#include <iostream>
#include <queue>

using namespace std;

static struct Project
{
    int cost;
    int profit;
};

static struct ProjectCostComparator
{
    bool operator()(const Project* p1, const Project* p2)
    {
        return p1->cost > p2->cost;
    }
};

static struct ProjectProfitComparator
{
    bool operator()(const Project* p1, const Project* p2)
    {
        return p1->profit < p2->profit;
    }
};

#define CLEAR_HEAP(heap) int size = head.size(); for (int i = 0; i < size; i++) { heap.pop(); }

static int maxProfit(const int* costs, const int* profits, size_t projectCount, int k, int m)
{
    Project* projects = (Project*)malloc(projectCount * sizeof(Project));
    memset(projects, 0, projectCount * sizeof(Project));

    for (int i = 0; i < projectCount; i++)
    {
        Project project = { costs[i], profits[i] };
        memcpy(projects + i, &project, sizeof(Project));
    }

    int originalMoney = m;
    int completedCount = 0;
    priority_queue<Project*, vector<Project*>, ProjectCostComparator> costHeap;
    priority_queue<Project*, vector<Project*>, ProjectProfitComparator> profitHeap;

    for (int i = 0; i < projectCount; i++)
    {
        costHeap.push(&projects[i]);
    }

    while (completedCount < k)
    {
        while (!costHeap.empty() && originalMoney >= costHeap.top()->cost)
        {
            auto top = costHeap.top();
            profitHeap.push(top);
            costHeap.pop();
        }

        if (!profitHeap.empty())
        {
            auto top = profitHeap.top();
            profitHeap.pop();
            originalMoney += top->profit;
            ++completedCount;
        }
        else
        {
            break;
        }
    }

    free(projects);
    return originalMoney - m;
}

// 输入:
// 正数数组costs
// 正数数组profits
// 正数k
// 正数m
// 含义：
// costs[i]表示i号项目的花费
// profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
// k表示你只能串行的最多做k个项目
// m表示你初始的资金
// 说明：
// 每做完一个项目，马上获得的收益，可以支持做下一个项目。
// 输出：
// 最后获得的最大钱数。
int main_IPO()
{
    int costs[]   = {2,4,5,13,3,};
    int profits[] = {3,6,8,20,1,};
    int k = 3;
    int m = 2;

    int totalProfit = maxProfit(costs, profits, sizeof(costs) / sizeof(int), k, m);
    printf("%d\n", totalProfit);

    return 0;
}